#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__

#include "common.h"

namespace algo
{

//Definition for singly-linked list.
template<typename T>
class LinkedList
{
private:

	struct Node {
		std::shared_ptr<T> val;
        std::shared_ptr<Node> next;

        Node() :  val(NULL), next(NULL) {    }
	};
public:
	LinkedList();

	virtual ~LinkedList();

	virtual std::shared_ptr<T> get(int index);
    virtual std::shared_ptr<T> getFirst();
    virtual std::shared_ptr<T> getLast();

	virtual void append(T new_val);
	virtual void add(int index, T obj);
	virtual void add(T obj);

    virtual bool remove(int index);
    virtual bool removeFirst();
    virtual bool removeLast();

    virtual void swap(int x, int y);

    virtual int size();
    virtual bool empty();

private:
	virtual std::shared_ptr<Node> getNode(int index)
	{
		if (index < 0 || index >= listSize)
		{
			throw index_out_of_bounds();
		}

		std::shared_ptr<Node> hNode = head;
		int c = 0;

		while (c <= index && hNode->next)
		{
			hNode = hNode->next;
			if (c == index)
			{
				break;
			}
			++c;
		}

		return hNode;
	}

    virtual std::shared_ptr<Node> getFirstNode()
	{
		return getNode(0);
	}

    virtual std::shared_ptr<Node> getLastNode()
	{
		return tail;
	}

protected:
    std::shared_ptr<Node> head = NULL;
    std::shared_ptr<Node> tail = NULL;
	int listSize  = 0;

};

template<typename T>
LinkedList<T>::LinkedList() : head(new Node), tail(head), listSize(0)
{
}

template<typename T>
LinkedList<T>::~LinkedList()
{
}

template<typename T>
void LinkedList<T>::append(T new_val)
{
    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<Node> p(new Node);
    p->val = new_data;
    p->next = tail->next;
    tail->next = p;
    tail = p;

    ++listSize;
}

template<typename T>
void LinkedList<T>::add(T new_val)
{
	append(new_val);
}

template<typename T>
void LinkedList<T>::add(int index, T new_val)
{
	if (index < 0 || index > listSize)
	{
		throw index_out_of_bounds();
	}

    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<Node> p(new Node);
    p->val = new_data;

    std::shared_ptr<Node> prevNode;
    if (0 == index)
    {
        prevNode = head;
    }
    else
    {
        prevNode = getNode(index - 1);
    }
    p->next = prevNode->next;
    if (!prevNode->next)
    {
        tail = p;
    }
    prevNode->next = p;

    ++listSize;
}

template<typename T>
bool LinkedList<T>::remove(int index)
{
	if (index < 0 || index >= listSize)
	{
		throw index_out_of_bounds();
	}

	std::shared_ptr<Node> prevNode(NULL);
	if (index == 0)
	{
		prevNode = head;
	}
	else
	{
		prevNode = getNode(index - 1);
	}

	prevNode->next = prevNode->next->next;
	if (!prevNode->next)
	{
		tail = prevNode;
	}
	
	return true;
}

template<typename T>
bool LinkedList<T>::removeFirst()
{
	return remove(0);
}

template<typename T>
bool LinkedList<T>::removeLast()
{
	return remove(listSize - 1);
}

template<typename T>
std::shared_ptr<T> LinkedList<T>::get(int index)
{
	return getNode(index)->val;
}

template<typename T>
std::shared_ptr<T> LinkedList<T>::getFirst()
{
	return getFirstNode()->val;
}

template<typename T>
std::shared_ptr<T> LinkedList<T>::getLast()
{
	return getLastNode()->val;
}

template<typename T>
void LinkedList<T>::swap(int x, int y)
{
	if (x < 0 || y < 0 || x >= listSize || y >= listSize || x == y)
	{
		throw index_out_of_bounds();
	}

	// x must less than y
	if (x > y)
	{
		int tmp = x;
		x = y;
		y = tmp;
	}

	std::shared_ptr<Node> prevX = NULL;
	std::shared_ptr<Node> prevY = NULL;

	std::shared_ptr<Node> hNode = head;
	int c = 0;

	while (hNode && !prevY)
	{
		if (c == x)
		{
			prevX = hNode;
		}

		if (c == y)
		{
			prevY = hNode;
		}

		++c;
		hNode = hNode->next;
	}

	std::shared_ptr<Node> pX = prevX->next;
	std::shared_ptr<Node> pY = prevY->next;

	hNode = y - 1 == x ? pX : pX->next;
	pX->next = pY->next;
	pY->next = hNode;

	prevX->next = pY;
	if (y - 1 != x)
	{
		prevY->next = pX;
	}

}

template<typename T>
int LinkedList<T>::size()
{
	return listSize;
}

template<typename T>
bool LinkedList<T>::empty()
{
	return 0 == size();
}


}	// namespace end


#endif